﻿#define  _CRT_SECURE_NO_WARNINGS 1


//描述
//现在有一个长度为 n 的正整数序列，其中只有一种数值出现了奇数次，其他数值均出现偶数次，请你找出那个出现奇数次的数值。
//输入描述：
//第一行：一个整数n，表示序列的长度。第二行：n个正整数ai，两个数中间以空格隔开。
//输出描述：
//一个数，即在序列中唯一出现奇数次的数值。
//https://www.nowcoder.com/practice/849b9e545f4742398d278f5dc4e003d2?tpId=182&&tqId=34478&rp=1&ru=/ta/exam-all&qru=/ta/exam-all/question-ranking
//#include <stdio.h>
//int main()
//{
//    int n = 0;
//    scanf("%d", &n);
//    int num = 0;
//    int k = 0;
//    int i = 0;
//    for (i = 0; i < n; i++)
//    {
//        scanf("%d", &k);
//        num ^= k;
//    }
//    printf("%d\n", num);
//    return 0;
//}



//描述
//给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。
//1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
//2.假设 nums[-1] = nums[n] = -\infty−∞
//3.对于所有有效的 i 都有 nums[i] != nums[i + 1]
//4.你可以使用O(logN)的时间复杂度实现此问题吗？
//如输入[2, 4, 1, 2, 7, 8, 4]时，会形成两个山峰，一个是索引为1，峰值为4的山峰，另一个是索引为5，峰值为8的山峰
//https://www.nowcoder.com/practice/fcf87540c4f347bcb4cf720b5b350c76?tpId=188&&tqId=38666&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking
//int findPeakElement(int* nums, int numsLen) {
//    // write code here
//    if (1 == numsLen)
//        return 0;
//    else if (*(nums) > *(nums + 1))
//        return 0;
//    else if (*(nums + numsLen - 1) > *(nums + numsLen - 2))
//        return numsLen - 1;
//    int i = 0;
//    for (i = 1; i < numsLen - 1; i++)
//    {
//        if (*(nums + i) > *(nums + i - 1) && *(nums + i) > *(nums + i + 1))
//            break;
//    }
//    return i;
//}

//优化
//int findPeakElement(int* nums, int numsLen) {
//    // write code here
//    if (1 == numsLen)
//        return 0;
//    else if (*(nums) > *(nums + 1))
//        return 0;
//    else if (*(nums + numsLen - 1) > *(nums + numsLen - 2))
//        return numsLen - 1;
//    int left = 0;
//    int right = numsLen - 1;
//    int mid = 0;
//    while (left < right)
//    {
//        mid = left + (right - left) / 2;
//        if (nums[mid] > nums[mid + 1])
//            right = mid;
//        else
//            left = mid + 1;
//    }
//    return left;
//}




//描述
//牛牛以前在老师那里得到了一个正整数数对(x, y), 牛牛忘记他们具体是多少了。
//但是牛牛记得老师告诉过他x和y均不大于n, 并且x除以y的余数大于等于k。
//牛牛希望你能帮他计算一共有多少个可能的数对。
//输入描述：
//输入包括两个正整数n, k(1 <= n <= 10 ^ 5, 0 <= k <= n - 1)。
//输出描述：
//对于每个测试用例, 输出一个正整数表示可能的数对数量。
//https://www.nowcoder.com/practice/bac5a2372e204b2ab04cc437db76dc4f?tpId=182&&tqId=34323&rp=1&ru=/ta/exam-all&qru=/ta/exam-all/question-ranking
//暴力求解：
//#include <stdio.h>
//int main()
//{
//    int n, k;
//    scanf("%d %d", &n, &k);
//    int x = 0;
//    int y = 0;
//    int num = 0;
//    for (x = 1; x <= n; x++)
//    {
//        for (y = k; y <= n; y++)
//        {
//            if (x % y >= k)
//                num++;
//        }
//    }
//    printf("%d\n", num);
//    return 0;
//}

//更优解法：
//假设输入 n = 10, k = 3 ；
//当 y <= k 时，意味着任何数字取模y的结果都在[0, k - 1]之间，都是不符合条件的。
//当 y = k + 1 = 4 时，x符合条件的数字有 3, 7 
//当 y = k + 2 = 5 时，x符合条件的数字有 3, 4, 8, 9
//当 y = k + 3 = 6 时，x符合条件的数字有 3, 4, 5, 9, 10
//当 y = k + n时， x小于y当前值，且符合条件的数字数量是：y - k个，
//                x大于y当前值，小于2 * y的数据中，且符合条件的数字数量是：y - k个
//从上一步能看出来，在y的整数倍区间内，x符合条件的数量就是(n / y) * (y - k)个 n / y 表示有多少个完整的 0 ~y区间，
//y - k 表示有每个区间内有多少个符合条件的数字
//最后还要考虑的是...往后这种超出倍数区间超过n的部分的统计 n % y 就是多出完整区间部分的数字个数，其中k以下的不用考虑，
//则符合条件的是 n % y - (k - 1) 个 这里需要注意的是类似于9这种超出完整区间的数字个数 本就小于k的情况，则为0
//最终公式：(n / y) * (y - k) + ((n % y < k) ? 0, (n % y - k + 1));
//#include <stdio.h>
//int main()
//{
//    long n, k;
//    scanf("%ld %ld", &n, &k);
//    if (k == 0)
//    {
//        printf("%ld\n", n * n);//任意数对的取模结果都是大于等于0的
//        return 0;
//    }
//    long count = 0;
//    for (long y = k + 1; y <= n; y++)
//    {
//        count += ((n / y) * (y - k)) + ((n % y < k) ? 0 : (n % y - k + 1));
//    }
//    printf("%ld\n", count);
//    return 0;
//}




//描述
//输入一个字符串和一个整数 k ，截取字符串的前k个字符并输出
//输入描述：
//1.输入待截取的字符串
//2.输入一个正整数k，代表截取的长度
//输出描述：
//截取后的字符串
//https://www.nowcoder.com/practice/a30bbc1a0aca4c27b86dd88868de4a4a?tpId=37&&tqId=21269&rp=1&ru=/ta/huawei&qru=/ta/huawei/question-ranking
//#include <stdio.h>
//int main()
//{
//    char str[101];
//    scanf("%s", str);
//    int n;
//    scanf("%d", &n);
//    str[n] = '\0';
//    printf("%s\n", str);
//    return 0;
//}